package com.zhz.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 409. 最长回文串
 * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
 * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
 * <p>
 * 示例 1:
 * 输入:s = "abccccdd"
 * 输出:7
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 * <p>
 * 示例 2:
 * 输入:s = "a"
 * 输入:1
 * <p>
 * 示例 3:
 * 输入:s = "bb"
 * 输入: 2
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindrome
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestPalindrome409 {

    public static void main(String[] args) {
        LongestPalindrome409 m = new LongestPalindrome409();
        String s = "abccccdd";
        int tmp = m.longestPalindrome(s);
        System.out.println(tmp);
    }

    /**
     * 预思路：
     * 使用set来查看时候有重复的，如果有重复的直接最大长度+2
     * 最后在判断set里面是不是空的，如果时空的，则直接返回sb的长度，否则sb的长度加1
     */
    public int longestPalindrome(String s) {
        int len = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                len += 2;
                set.remove(c);
            } else {
                set.add(c);
            }
        }
        return set.isEmpty() ? len : len + 1;
    }


    public int longestPalindrome1(String s) {


        return 0;
    }

}
